//给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 
//
// 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 
//
// 注意: 
//不能使用代码库中的排序函数来解决这道题。 
//
// 示例: 
//
// 输入: [2,0,2,1,1,0]
//输出: [0,0,1,1,2,2] 
//
// 进阶： 
//
// 
// 一个直观的解决方案是使用计数排序的两趟扫描算法。 
// 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 
// 你能想出一个仅使用常数空间的一趟扫描算法吗？ 
// 
// Related Topics 排序 数组 双指针 
// 👍 564 👎 0

package leetcode.editor.cn;

//Java：颜色分类
public class P75SortColors {

    /**
     * 思路：直接选择排序, 注释的还有网上的一种思路，就是利用双指针 将0都放到数组左边，2都放到数组右边，这样最后数据就是排好序的。执行用时也会比较少
     * <p>
     * 执行用时： 1 ms , 在所有 Java 提交中击败了 10.55% 的用户 内存消耗： 38.2 MB , 在所有 Java 提交中击败了 50.67% 的用户
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void sortColors(int[] nums) {
            sort(nums);
        }

        // 按数组的第一个元素从小到大排序
        private void sort(int[] nums) {

//            int left = 0;
//            int right = nums.length - 1;
//            int i = 0;
//            while (i <= right) {
//                if (nums[i] == 0) {
//                    swap(nums, i, left);
//                    left++;
//                    i++;
//                } else if (nums[i] == 2) {
//                    swap(nums, i, right);
//                    right--;
//                } else {
//                    i++;
//                }
//            }

            for (int i = 0; i < nums.length; i++) {
                int min = i;
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[j] < nums[min]) {
                        min = j;
                    }
                }
                swap(nums, i, min);
            }
        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P75SortColors().new Solution();
        int[] nums = new int[]{1, 2, 0};
        solution.sortColors(nums);
        System.out.println(nums);
        // TO TEST
    }

}